package leetcode.dynamic;

import java.util.HashMap;
import java.util.HashSet;

public class Lc403 {

    HashMap<Integer, Integer> map;
    boolean[][] cannotCross;
    public boolean canCross(int[] stones) {

        if (stones[1] > stones[0] + 1)
            return false;
        map = new HashMap<>(); // key 石头所在的单元格，val 在stones中的下标
        cannotCross = new boolean[stones.length][stones.length + 1];
        for (int i = 0; i < stones.length; i++) {
            map.put(stones[i], i);
        }
        return getTry(stones, 1, 1);
    }

    //getTry(curIndex, k) = 任意getTry(nextIdex, nk)
    private boolean getTry(int[] stones, int curIndex, int k) {
        if (cannotCross[curIndex][k])
            return false;
        if (curIndex == stones.length - 1)
            return true;
        int rangeL = stones[curIndex] + k - 1;
        int rangeR = stones[curIndex] + k + 1;
        rangeL = rangeL <= stones[curIndex] ? stones[curIndex] + 1 : rangeL;
        for (int i = rangeL; i <= rangeR ; i++) {
            if (map.containsKey(i)) { //在单元格i上有石头
                if (getTry(stones, map.get(i), i - stones[curIndex])) {
                    return true;
                } else cannotCross[map.get(i)][i - stones[curIndex]] = true;

            }
        }
        cannotCross[curIndex][k] = true;
        return false;
    }


    public static void main(String[] args) {
        int[] arr = {0,1,2,3,4,8,9,11};
        Lc403 lc403 = new Lc403();
        System.out.println(lc403.canCross(arr));
    }
}
